/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._268;

/**
 *
 * 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
 *
 * 示例 1:
 *
 * 输入: [3,0,1]
 * 输出: 2
 * 示例 2:
 *
 * 输入: [9,6,4,2,3,5,7,0,1]
 * 输出: 8
 * 说明:
 * 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._268
 * @ClassName: MissingNumber
 * @Author: linyaonan
 * @Date: 2019/12/18 17:03
 */
public class MissingNumber {
    public int missingNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        long r = 0;
        for (int num : nums) {
            r += num;
        }
        long add = (nums.length)* (nums.length + 1) / 2;
        return (int) (add - r);
    }

}
